맨 앞 삽입에서는 새 노드의 next를 먼저 연결해야 한다
삽입은 자리를 찾는 일(Θ(1+i))과 참조 두 개를 고치는 일(Θ(1))로 나뉜다. 두 대입의 순서를 바꾸면 맨 앞 삽입에서만 기존 노드로 가는 참조가 사라진다.
현재 상태
실행 단계
기존 노드를 가리키는 참조가 하나뿐이면 그 참조를 바꾸기 전에 새 노드의 next를 먼저 연결한다.
삭제는 앞 노드의 next를 삭제할 노드의 다음 노드로 바꾼다
중간 노드를 삭제할 때는 앞 노드의 next가 삭제할 노드의 다음 노드를 가리키게 한다. 첫 노드는 앞 노드가 없으므로 head를 직접 바꾼다. 끝 노드를 지우면 tail도 앞 노드로 옮기고, 어느 경우든 n을 1 줄인다.
tail은 마지막 노드를 가리키는 참조다. 아래 코드 칸에서 짙은 칸이 실행한 줄이다.현재 상태
삭제 위치 찾기
참조 변경
원소 수
참조와 n을 고치는 일은 Θ(1)이지만, i번째 노드를 삭제하려면 그 위치까지 순회해야 하므로 전체 비용은 Θ(1+i)이다. 정리하면 순회 Θ(n), 탐색 최악 Θ(n), 맨 앞 삽입 Θ(1), i에 삽입과 i에서 삭제는 Θ(1+i)다.